package com.spirng.leetcode.day08;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Test47 {
    public static void main(String[] args) {
        Test47 test47 = new Test47();
        test47.permuteUnique(new int[]{1,2,3});

    }
    ArrayList<List<Integer>> lists=new ArrayList<>();
    ArrayList<Integer> list=new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
            int [] use=new int [nums.length];
            backtracking(nums,use);
            return lists;
    }
    public void  backtracking(int[] nums,int [] use){
         if(list.size()== nums.length){
             lists.add(new ArrayList<>(list));
             return;
         }
        HashSet set=new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])||use[i]==1){
                continue;
            }
            set.add(nums[i]);
            list.add(nums[i]);
            use[i]=1;
            backtracking(nums,use);
            list.remove(list.size()-1);
            use[i]=0;
        }
    }
}
